
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1713. -- [Usaco2007 China]The Bovine Accordion and Banjo Orchestra -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1713: [Usaco2007 China]The Bovine Accordion and Banjo Orchestra</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>71&nbsp;&nbsp;<span class=green>Solved: </span>16<br>[<a href='submitpage.php?id=1713'>Submit</a>][<a href='problemstatus.php?id=1713'>Status</a>][<a href='bbs.php?id=1713'>Discuss</a>]</center><h2>Description</h2><div class=content>The 2*N (3 <= N <= 1,000) cows have assembled the Bovine Accordion
and Banjo Orchestra!  They possess various levels of skill on their
respective instruments: accordionist i has an associated talent
level A_i (0 <= A_i <= 1,000); banjoist j has an associated talent
level B_j (0 <= B_j <= 1,000).

The combined `awesomeness' of a pairing between cows with talents
A_i and B_j is directly proportional to the talents of each cow in
the pair so a concert with those two cows will earn FJ precisely
A_i * B_j dollars in "charitable donations".  FJ wishes to maximize
the sum of all revenue obtained by his cows by pairing them up in
the most profitable way.

有二个数列，每行N个。你可以将第一行的某个数A与第二行的某个B连接起来，得到的收益为这两个数的乘积 
而A之前的那些没有连线的数，将其值累加起来再平方，这个数为你的损失，B之前的那些没有连线的数将其值 
累加起来再平方，这个数也为你的损失,现在希望你的收益值越大越好，请问其值可以为多少？ 
注意你所连出来的线不能交叉 


Input 

第一行给出数字N, (3 <= N <= 1,000) 
下面N行给出第一个数列的N个数,其值在[0,1000] 
再下面N行给出第二个数列的N个数其值在[0,1000] 


Output 

你的最大收益值. 

Unfortunately, FJ's accordionists are a bit stuck up and stubborn.
If accordionist i is paired with banjoist j, then accordionists
i+1..N refuse to be paired with banjoists 1..j-1. This creates
restrictions on which pairs FJ can form. FJ thus realizes that in
order to maximize his profits, he may have to leave some cows
unpaired.

To make matters worse, when one or more of the musicians is skipped,
they will be greatly upset at their wasted talent and will engage
in massive binge drinking to wash away their sorrows.

After all pairings are made, a list is constructed of the groups
of each of the consecutive skipped musicians (of either instrument).
Every group of one or more consecutive skipped cows will gather
together to consume kegs of ice cold orange soda in an amount
proportional to the square of the sum of their wasted talent.

Specifically, FJ has calculated that if the x-th to y-th accordionists
are skipped, they will consume precisely (A_x + A_x+1 + A_x+2 + ...
+ A_y)^2 dollars worth of orange soda in the process of drinking
themselves into oblivion. An identical relationship holds for the
banjoists. FJ realizes that he'll end up getting stuck with the
bill for his cows' drinking, and thus takes this into account when
choosing which pairings to make.

Find the maximum amount of total profit that FJ can earn after the
contributions are collected and the orange soda is paid for.
</div><h2>Input</h2><div class=content>* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains the single integer: A_i

* Lines N+2..2*N+1: Line i+N+1 contains the single integer: B_i

</div><h2>Output</h2><div class=content>* Line 1: A single integer that represents the maximum amount of cash
        that FJ can earn.

</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>3<br />
1<br />
1<br />
5<br />
5<br />
1<br />
1<br />
<br />
INPUT DETAILS:<br />
<br />
There are 6 cows: 3 accordionists and 3 banjoists. The accordionists have<br />
talent levels (1, 1, 5), and the banjoists have talent levels (5, 1, 1).<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>17<br />
<br />
OUTPUT DETAILS:<br />
<br />
FJ pairs accordionist 3 with banjoist 1 to get earn A_3 * B_1 = 5 * 5 = 25<br />
in profit.  He loses a total of (1 + 1)^2 + (1 + 1)^2 = 8 dollars due to<br />
the cost of soda for his remaining cows. Thus his final (net) profit is 25<br />
- 8 = 17.<br />
</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Gold'>Gold</a></p></div><center>[<a href='submitpage.php?id=1713'>Submit</a>][<a href='problemstatus.php?id=1713'>Status</a>][<a href='bbs.php?id=1713'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
